Information and Control

How to solve IMO P2/5

Information

The structure of most problems in Mathematics is usually very familiar; they usually give you some sort of structure with a set of constraints, perhaps a sequence with some condition between terms, a set of points constructed from triangle $A B C$ , a function with a functional equation attached to it or even just the fact that $a$ , $b$ and $c$ are integers satisfying some equation.

They then ask you to prove some particular results from the information you are given.

But sometimes it seems like there is nothing you can even do, how you even start, how do you make progress?

We have to remember that all the information you need to solve the problem is given to you, we already know that what we are trying to do should be possible, maybe we drew the diagram a couple of times and yup, it's true, or maybe we tried our small cases and we always go the same answer. Also in the context of an exam, if the problem was impossible it wouldn't be a problem given to you.

Anyway, all the information you need to solve a problem is in the problem, it's just in a form that is not particularly useful to you.

So the goal in solving problems is taking the information you are given and transforming it into forms that are useful. You can imagine each piece of information as being a mine with a bunch of juicy ores inside it and then the rest of it being garbage useless rocks which you don't care about, your job is to extract out the diamonds.

For example in the case of 2022 IMO P5

Potential Spoilers

The $b!$ actually tells us a lot of information, it being the product of all the terms from $1$ to $b$ . A key step in how I solved the problem is transforming this to a much more useful piece of information which is that when $b < p$ , $b!$ and $p$ must have no prime divisors smaller than $p$ which becomes extremely useful. After we finish transforming this piece of information we can discard the original information and just use this new piece of information for pretty much the remainder of the problem.

I would also like to mention a technique I learnt from Tony Wang, if you want to be sure if a particular piece of information is necessary, just remove it. Then you can draw your diagram again, try your cases again and if things stop working you know that condition was actually important, otherwise it's not strictly necessary.

However sometimes we should be careful when throwing away information once it has been transformed into another form. You have to be careful that sometimes when you transform a piece of information into a more useful form, you lose some of the information you started with. Most of the time you can intuitively feel when you've exhausted all the diamonds in a mine, however some particularly clever problems will have you re using the same piece of information in many different ways so just be careful not to forget about it and toss it aside.

Even if the information you have left over is technically sufficient in solving a problem sometimes it is just harder, the obvious example of this is converting a geometry problem to a purely projective statement. It might technically use less points and thus appear simpler, but it might also become harder as you lose out on angles which are unreasonably effective in euclidean geometry.

Control

For most of my problem solving journey I've only considered Information, however eventually I realised that there was some axis in the problem solving process that couldn't fully be captured by Information alone.

The key to solving pretty much every problem is to view the problem in a way that gives you the most control.

The key to constructing points is to pick points that give you the most useful information, constructions are not created equal, and the key to figuring out the best one is finding the one that gives you good stuff and in the context of geo, it means having angles that are easy to chase.

In a combinatorics problem the key to deciding whether to view the problem as a graph, whether to try a global bounding argument or whether to analyse moves individually comes down to which method gives you the most useful information about the problem.

You could this of the concept of control as adding a heuristic to Dijkstra's algorithm to create A*. Acting off of just Information we start at the problem statement, make transformations to our information which can be seen as moving between states until we eventually end up at the solution state. Control gives you a heuristic in deciding which steps probably are good and which probably are bad.

ISL 2024 A5

I'm going to end with a discussion of how I solved 2024 ISL A5. Which I almost solved in a mock but didn't because I ran out of time right as I figured out the final line. Skip to the end if you just want the conclusions.

Find all periodic sequence $a_1,a_2,\dots$ of real numbers such that the following conditions hold for all $n\geqslant 1$ :
$a_{n+2}+a_n^2=a_n+a_{n+1}^2\quad\text{and}\quad |a_{n+1}-a_n|\leqslant 1.$

Definite Spoilers

So immediately I played around with the equation, seeing if I can rearrange it into a more useful form.

a_{n+2} - a_n = a_{n+1}^2 - a_{n}^2

The condition we are given is between consecutive terms, so we also want consecutive terms in our equation. Let's just will it into existence on the left hand side:

a_{n+2} - a_n - (a_{n+1} - a_n) = a_{n+1}^2 - a_{n}^2 - (a_{n+1} - a_n)

a_{n+2} - a_{n+1} = (a_{n+1}-a_n)(a_{n+1}+{a_n} - 1)

Notice that if $a_{n+1} - a_n$ is ever equal to $0$ then $a_{n+2} - a_{n+1} = 0$ and so on, then all consecutive differences must be equal to zero due to periodicity.

Which yields the solution set $a, a, a, \dots$ for any real number $a$ .

Now assuming the consecutive differences between terms is never $0$ we have that

(a_{n+1}+a_n-1)(a_{n+2}+a_{n+1}-1) \dots (a_{n+d}-a_{n+d-1} - 1) = 1

But it turns out that this is not very useful right now, the reason being it doesn't use the information that the difference between consecutive terms has magnitude less than $1$ .

So we go back a few steps and change our approach

a_{n+2} - a_n + (a_{n+1} + a_n) = a_{n+1}^2 - a_{n}^2 + (a_{n+1} + a_n)

a_{n+2} + a_{n+1} = (a_{n+1}-a_n)(a_{n+1} - a_{n} + 1)

I would like to remark now that this is a very "global" result meaning that we care very little about the individual terms themselves but instead about the sequence as a whole which is in contrast to other problems where looking at terms individually gives you a lot of insight.

When doing this problem I was sure this was the way to do it because it seemed to give me a lot of control over the problem

Which tells us that either $a_{n+1} - a_n = 0$ for all terms which yields the solution set $a, -a, a, -a, \dots$ for all real numbers $a$ where $|a| \le \frac 1 2$ .

Or that

(a_{n+1}-a_n+1)(a_{n+2}-a_{n+1}+1) \dots (a_{n+d}-a_{n+d-1} + 1) = 1

This lets us use the condition that $a_{n+1} - a_n \ge -1$ and in fact $a_{n+1} - a_n > -1$ as the product of $(a_{n+1} - a_n +1) \neq 0$ .

This means that each $a_{i+1} - a_i + 1$ term is positive, which actually gives us a lot of control now and inspired us to use inequalities as they work well with positive integers.

Applying AM/GM we get that

\prod (a_{i+1} - a_{i} + 1)^{1/d} \ge \frac {\sum (a_{i+1} - a_i + 1)} {d}

But notice that as $a$ is periodic with period $d$ the sum of $d$ consecutive differences is always going to be $d$ .

\prod (a_{i+1} - a_{i} + 1) \ge 1^{d} = d

with equality happening only when $a_{i+1} - a_i + 1 = D$ is a constant.

Note $D^d = 1$ hence $D = 1$ . Therefore this is only possible when $a_{i+1} -a_i$ is $0$ for all $i$ which we've already covered.

So we have found all solution sets.

I think I wrote down the main idea with the product being $= 1$ right at the start, I even wrote "This is the main idea" however I got distracted trying wacky thing that in hindsight obviously would have have worked.

In the last few minutes I could only scribble out "Jensen" once I had the product and sum conditions that were enough to use AM/GM, I knew exactly how to do this inequality I just didn't have time to write it

I ended up getting a $2/7$ for this problem, which is outrageous considering I was literally one single line away from solving it, and it's not even a situation where because I didn't write that one line I didn't write the lines afterwards and therefore it's not enough, no, I literally wrote stuff like "If we can prove this can't be the case blah blah blah, now I just need to prove this".

The End

If you are stuck, don't just try random things, think about what you have tried and what things you have a lot of control over.
Remember what information you've been given, figure out what information is important and what information you still need to use.
Don't throw away information prematurely.
Finally, Believe in yourself.